1. Field of the Invention
This invention relates to apparatus and methods for image data compression.
2. Description of the Prior Art
In an image data compression system, often the output bit rate of a compressed data stream is constrained by the capacity of a transmission or storage channel. A particular example of this is when compressed video data has to be recorded on a tape channel; generally, to maintain real-time operation, a whole field or frame's worth of compressed data has to be recorded onto a predetermined number of record tracks.
In order to comply with this constraint, the bit rate of the output compressed data is controlled by controlling the degree of compression applied. In many cases, this is achieved through controlling a quantization factor applied to the video data (e.g. after transformation to the frequency domain).
The effect of varying the quantization factor on the quantity of compressed data is highly non-linear and not easily predictable. This means that a suitable quantization factor can be chosen accurately only by performing trial compressions.
One previously proposed way of performing trial compressions is the so-called binary search. This is an iterative process whereby a first trial quantization is performed using a quantization factor of, say, one half of the available range. Subsequent stages of trial quantization are performed at values which are either less than or greater than the quantization factor used in the preceding stage, depending on whether the preceding stage produced too much or too little compressed data. The increment or decrement applied between stages decreases with each stage, in order to iterate towards a correct value.
For example, if the available range of quantization values is from 1 to 64, in a binary search technique a first trial quantization might be performed at a quantization value of 32. Depending on whether this produces too much or too little output data, the second stage might use a value of either 48 or 16, i.e. 32.+-.16. A third stage would then use one of 8, 24, 40 or 56, i.e. (48 or 16).+-.8, and so on. At the final stage, the most appropriate of all of the values tested (i.e. the value generating a data amount nearest to, but under, the available bit rate) is selected for use in compressing that input data.
So, in the above example, six stages of trial compression are needed to select a quantization value in the range from 1 to 64. A perceived advantage of this arrangement is that it avoids the need to perform 64 trial compressions to select a quantization value.
However, one drawback of the binary search technique is that the stages of trial compression must be performed consecutively, because the results of each stage are needed before the quantization value to be used in the next stage can be chosen. This imposes a considerable delay on the data compression system--a problem not only because of the actual time delay applied to the data, but also because substantial amounts of memory are required to store the input data for the delay period. The specific example above requires six delay periods for the binary search process. This can be difficult to implement where the apparatus is embodied, for example, as an application specific integrated circuit (ASIC).
It is an object of the invention to provide an improved technique for selecting quantization values to be used in data compression.